class Solution {
public:
    int fib(int n) {
        vector<vector<int>> vt = { { 0, 1 } };
        vector<vector<int>> muti = { { 1, 1 } , { 1, 0 } };
        vector<vector<int>> tmp = { { 1, 0 } , { 0, 1 } };
        while (n > 0)
        {
            if ((n & 1) != 0)
                tmp = mutiply(tmp, muti);
            muti = mutiply(muti, muti);
            n >>= 1;
        }
        vector<vector<int>> ans(2, vector<int>(2));
        ans = mutiply(vt, tmp);
        return ans[0][0];
    }
    vector<vector<int>> mutiply(vector<vector<int>>& vt1, vector<vector<int>>& vt2)
    {
        int m = vt1.size();
        int n = vt2[0].size();
        int k = vt1[0].size();
        vector<vector<int>> ans(m, vector<int>(n));
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                for (int p = 0; p < k; p++)
                {
                    ans[i][j] += vt1[i][p] * vt2[p][j];
                }
            }
        }
        return ans;
    }
};